Search results for "Dominating set"

Construction of Disjoint Virtual Backbones for Wireless Sensor Networks

2020

A wireless sensor network is a wireless network of sensors aimed at monitoring physical events. It has ingratiated itself into almost all areas of human endeavors. Data dissemination in these networks is quite challenging and is generally accomplished by flooding. But flooding introduces broadcast storm problem due from implosion and overlap. To overcome this, topology management can prescribe a virtual backbone network to which routing is confined. In this paper we propose an algorithm that constructs multiple disjoint virtual backbone networks, using only nodes' locations. The disjointedness makes routing more robust and the network exploitation energy efficient. Simulations show our algo…

A Restricted-Weakly Connected Dominating Set for Role Assignment in a Multichannel MAC for Wireless Mesh Network

2009

International audience; We propose an efficient way of constructing the wireless mesh structure associated with Molecular MAC, a multichannel access method designed for efficient packet forwarding. We base our role assignment on a restricted Weakly Connected Dominating Set structure. After presenting a formal definition of the role assignment problem, we prove its NP-completeness. Then, we propose a centralized 2-approximation algorithm that maximizes the sum of radio link capacities in the molecular structure. Finally, we extend this protocol so that it can operate in a distributed way still providing the same guarantee. This distributed protocol is self-stabilizing thus robust to topology…

On the hardness of optimization in power-law graphs

2008

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…

Estimating the length of minimal spanning trees in compression of files

1984

Compression of a formatted file by a minimal spanning tree (MST) is studied. Here the records of the file are considered as the nodes of a weighted undirected graph. Each record pair is connected in the graph and the corresponding arc is weighted by the sum of field lengths of those fields which differ in the two records. The actual compression is made by constructing an MST of the graph and by storing it in an economic way to preserve the information of the file. The length of the MST is a useful measure in the estimation of the power of the compression. In the paper we study upper bounds of this length, especially in the case where the field lengths of the different fields may vary. The u…

Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees

2017

International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…

Distributed Coverage of Ego Networks in F2F Online Social Networks

2016

Although most online social networks rely on a centralized infrastructure, several proposals of Distributed Online Social Networks (DOSNs) have been recently presented. Since in DOSNs user profiles are stored on the peers of the users belonging to the network, one of the main challenges comes from guaranteeing the profile availability when the owner of the data is not online. In this paper, we propose a DOSN based on a friend-to-friend P2P overlay where the user's data is stored only on friend peers. Our approach is based on the ego-network concept, which models the social network from the local point of view of a single user. We propose a distributed algorithm which is based on the notion …

Evaluation and improvement of collective flooding in WSNs with various link correlations

2015

One of the main challenges confronted by wireless sensor networks (WSNs) is to reduce energy consumption of nodes for the purpose of network lifetime extension. In the literature, many backbone based protocols such as connected dominating set (CDS) and broadcast or multicast based protocols are employed in order to improve network performance in terms of metrics like energy consumption, number of transmissions and dissemination delay. In this paper, we evaluate the performance of a recently proposed transmission protocol known as collective flooding (CF), which is based on link correlation, under various link correlation conditions. Through simulations and analyses we demonstrate that altho…

MAC strategies for single rendezvous multi-hop cognitive radio networks

2009

This paper presents two MAC strategies for multi-hop cognitive radio networks in single radio multi-channel cases. Both strategies use one of the idle multiple channels for communication among secondary users, and the network will leave the current channel and jump to another channel as a group if any primary user appears. The first strategy is based on a pre-defined pattern that will always tune to the next available channel when primary user emerges. The second one is based on the concept of connected dominating set in which a backbone is formed in the network in order to keep the continuity of the communication. The strategies are evaluated in both homogeneous and heterogeneous channels …

2021